package leetcode.search;

import java.util.*;

/**
 给定一个可包含重复数字的序列 nums ，
 按任意顺序 返回所有不重复的全排列。
 */
public class PermuteUnique47 {

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean []used = new boolean[nums.length];
        List<List<Integer>> res = new ArrayList<>();

        permuteUnique2(used,nums,res, new LinkedList<>(),0, nums.length);
        return res;

    }


    private void  permuteUnique2(boolean []used, int []nums, List<List<Integer>> res, LinkedList<Integer> path,int index, int n){
        if(index==n){
            res.add(new ArrayList<>(path));
        }


        for (int i = 0; i < n; i++) {
            if(used[i])
                continue;

            if(i>0 && nums[i]==nums[i-1] && !used[i-1])
                continue;

            used[i] = true;
            path.add(nums[i]);
            permuteUnique2(used,nums,res,path,index+1,n);
            path.removeLast();
            used[i] = false;
        }

    }
}